// 给定一个列表temperatures，temperatures[i]表示第i天的气温
// 要求输入一个列表，每个位置代表 ‘如果要观测到更高的气温，至少需要等待的天数’，如果之后气温不再升高，则用0来代替

// 思路：给定一个数组，对于每个位置，在该位置右侧找到一个比当前元素更大的元素，求该元素与右侧第一个比当前元素更大的元素之间的距离
// 将所有距离保存为数组返回结果
// 使用单调递减栈，栈中保存元素的下标

// 1. 首先将答案数组ans全部赋值为0，遍历数组每个元素
// 2. 如果栈为空，则将当前元素的下标入栈
// 3. 如果栈不为空，且当前数字大于栈顶元素对应数字，则栈顶元素出栈，并计算下标差
// 4. 此时当前元素就是栈顶元素的下一个更高值，将其下标差存入答案数组ans中保存起来，判断栈顶元素
// 5. 直到当前数字小于或等于栈顶元素，则停止出栈，将当前元素下标入栈
// 6. 输出答案数组ans

// 时间复杂度：O(n)。
// 空间复杂度：O(n)
const Stack  = require('../1. 堆栈基础/1. 堆栈的顺序存储实现')
function dailyTemeratures(arr) {
    let len = arr.length
    let stack = new Stack()
    let ans = new Array(len).fill(0)

    for (let i = 0; i < len; i++) {
        while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
            let index = stack.pop()
            ans[index] = i - index
        }  
        stack.push(i)
    }
    return ans
}

let temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
console.log(dailyTemeratures(temperatures));